using namespace std;
template<typename DT>

class DoubleLinkedList
{
    private:
        //The Node class includes the stored item and pointers to the previous and next nodes.
        struct Node
        {
            DT data;
            Node *prev;
            Node *next;

            Node(const DT & d = DT{ },Node *p = nullptr, Node *n = nullptr)
              : data{ d }, prev{ p }, next{ n } { }

            Node(DT && d, Node *p = nullptr, Node *n = nullptr)
              : data{ move(d) }, prev{p}, next {n} { }
        };

    public:
        //The declaration of the public nested class const_iterator.
        class const_iterator
        {
            public:
              //It's the public constructor in the class const_iterator.
              const_iterator( ) : current{ nullptr }
                { }

              //Return the object stored at the current position.
              const DT & operator* ( ) const
                { 
                  assertIsValid();
                  return retrieve();
                }

              //The implementation of operator++ .
              //Write seperate routines for the prefix and postfix versions, and
              //use the parameter 'int' to distinguish them and state different semantics.
              const_iterator & operator++ ( )     //The pointer move to the next node.
              {
                  assertIsValid();
                  current = current->next;
                  return *this;
              }

              const_iterator operator++ (int)
              {
                  assertIsValid();
                  const_iterator old = *this;
                  ++( *this );
                  return old;
              }

              const_iterator & operator-- ( )     //The pointer move to the previous node.
              {
                  assertIsValid();
                  current = current->prev;
                  return *this;
              }

              const_iterator operator-- (int)
              {
                  assertIsValid();
                  const_iterator old = *this;
                  --(*this);
                  return old;
              }

              bool operator==( const const_iterator & rhs ) const
                { return current == rhs.current; }
              bool operator!=( const const_iterator & rhs ) const
                { return !(*this == rhs); }

            protected:
              //Mark them as protected members in order to only allow classes 
              //that inherit from them to have access to them.
              Node *current;
              const DoubleLinkedList<DT> *theList;

              //Protected helper in const_iterator that returns the object
              //stored at the current position.
              //It can be called by all three versions of operator* without any type conversions.
              DT & retrieve( ) const
                { return current->data; }

              //The protected constructor in the class const_iterator.
              const_iterator( const DoubleLinkedList<DT> & lst, Node *p ) 
                : theList{ &lst }, current{ p }
              {  
              }

              //In order to perform additional error checks.
              //When the list is empty or other special cases, it throws
              //an exception. 
              //If we want the function to be effective, we need to change the number
              //of parameters of all calls to constructors of classes iterator and
              //const_iterator from one to two.
              void assertIsValid( ) const
              {
                  if( theList == nullptr || current == nullptr || current == theList->head )
                      throw "The iterator is out of bounds.";
              } 

              //The friend declaration grants the DoubleLinkedList class access to protected members.
              friend class DoubleLinkedList<DT>;  

        };

        //The declaration of the public nested class iterator.
        //Use the inheritance syntax to state that the class iterator
        //has the same functionality as const_iterator.
        class iterator : public const_iterator
        {
            public:
              iterator( )
                { }

              DT & operator* ( )
              { 
                  return const_iterator::retrieve( );
              }
              const DT & operator* ( ) const
              { 
                  return const_iterator::operator*( );
              }

              iterator & operator++ ( )
              {
                  this->current = this->current->next;
                  return *this;
              }

              iterator operator++ (int)
              {
                  iterator old = *this;
                  ++(*this);
                  return old;
              }

              iterator & operator-- ( )
              {
                  this->current = this->current->prev;
                  return *this;
              }
              iterator operator-- (int)
              {
                  const_iterator old = *this;
                  --(*this);
                  return old;
              }

            protected:
              //It's the protected constructor in the class iterator.
              //Use an initialization list to initialize the inherited current node.
              iterator( const DoubleLinkedList<DT> & lst, Node *p ) : const_iterator(lst,p)
                { }

              friend class DoubleLinkedList<DT>;
        };

    public:
        //The constructor and Big-Five of the class DoubleLinkedList.

        //It's the public constructor in the class DoubleLinkedList.
        DoubleLinkedList( )
          { init( ); }

        //It's the public destructor in the class DoubleLinkedList.
        ~DoubleLinkedList( )
        {
            clear( );
            delete head;
            delete tail;
        }

        //It's the public copy constructor in the class DoubleLinkedList.
        DoubleLinkedList ( const DT & rhs )
        {
            init( );
            for( auto & x : rhs )
                push_back(x);
        }

        //It's the public copy assignment in the class DoubleLinkedList.
        DT & operator= (const DT & rhs)
        {
            DoubleLinkedList copy = rhs;
            swap( *this , copy );
            return *this;
        }

        //It's the public move constructor in the class DoubleLinkedList.
        DoubleLinkedList (DT && rhs)
          : theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail}
        {
            rhs.theSize = 0;
            rhs.head = nullptr;
            rhs.tail = nullptr;
        }

        //It's the public move assignment in the class DoubleLinkedList.
        DT & operator= ( DT && rhs)
        {
            swap( theSize, rhs.theSize );
            swap( head, rhs.head );
            swap( tail, rhs.tail );

            return *this;
        }

        //Return the first node(the next one of the header node) of the list.
        iterator begin( )
          {
              iterator itr{ *this, head };
              return ++itr;
          }
        const_iterator begin( ) const
          { 
              const_iterator itr{ *this, head };
              return ++itr;
          }

        //return the tail node of the list.
        iterator end( )
          {
              iterator itr{ *this, tail };
              return itr;
          }
        const_iterator end( ) const
          {
              iterator itr{ *this, tail};
              return itr;  
          }

        int size( ) const         //Return the size of the list.
          { return theSize; }
        bool empty( ) const       //Judge if the list is empty.
          { return size()==0;}

        //remove items until the list is empty.
        void clear( )
        {
            while( !empty( ) )
                pop_front( );
        }

        //Methods in the class DoubleLinkedList.
        DT & front( )
          { return *begin( ); }
        const DT & front( ) const
          { return *begin( ); }
        DT & back( )
          { return *--end( ); }
        const DT & back( ) const
          { return *--end( ); }
        void push_front( const DT & x)         //Insert a data at the front.
          { insert( begin( ),x ); }
        void push_front( DT && x)
          { insert( begin( ),move(x) ); }
        void push_back( const DT & x)          //Insert a data at the back.
          { insert( end( ),x ); }
        void push_back( DT && x)
          { insert( end( ),move(x) ); }
        void pop_front( )                      //Move out a data at the front.
          { erase( begin( ) ); }
        void pop_back( )                       //Move out a data at the back.
          { erase( --end( ) ); }

        //Insert x before itr.
        iterator insert(iterator itr, DT && x)
        {
            itr.assertIsValid( );
            if( itr.theList != this )
                throw "The iterator mismatches.";
            Node *p = itr.current;
            theSize++;
            return { *this, p->prev = p->prev->next = new Node{ move(x), p->prev, p } };
        }

        //Insert x before itr.
        iterator insert( iterator itr, const DT & x )
        {
            itr.assertIsValid( );
            if( itr.theList != this )
                throw "The iterator mismatches.";
            Node *p = itr.current;
            theSize++;
            return { *this, p->prev = p->prev->next = new Node{ x, p->prev, p } };
        }

        //Erase item at itr.
        iterator erase( iterator itr )
        {
            Node *p = itr.current;
            itr.assertIsValid();
            if(itr.theList != this)
                throw "The iterator mismatches.";
            iterator retVal{ *this, p->next };
            p->prev->next = p->next;
            p->next->prev = p->prev;
            delete p;
            theSize--;

            return retVal;
        }

        //Erase items between the node of the pointer 'from' and
        //the previous one of the node of the pointer 'to'.
        iterator erase( iterator from, iterator to )
        {
            for(iterator itr = from; itr != to;)
            {
                itr.assertIsValid();
                if(itr.theList != this)
                    throw "The iterator mismatches.";
                itr = erase(itr);
            }
            return to;
        }

    private:
        //The data members of the class List,including the size,the pointers to the header and tail nodes.
        int theSize;
        Node *head;
        Node *tail;

        //Creates an empty List.
        //In order to allow the zero-parameter and copy constructors
        //to allocate the header and tail nodes.
        void init( )
        {
            theSize = 0;
            head = new Node;
            tail = new Node;
            head->next = tail;
            tail->prev = head;
        }

};